“School of Biological Sciences”

Back to Papers Home
Back to Papers of School of Biological Sciences

Paper   IPM / Biological Sciences / 13468
School of Biological Sciences
  Title:   Do Triplets Have Enough Information to Construct the Multi-Labeled Phylogenetic Tree?
  Author(s): 
1.  R. Hassanzadeh.
2.  C. Eslahchi.
3.  W. Sung.
  Status:   Published
  Journal: Plos One
  No.:  7
  Vol.:  DOI: 10.1371/journal.pone.0103622
  Year:  2014
  Supported by:  IPM
  Abstract:
The evolutionary history of certain species such as polyploids are modeled by a generalization of phylogenetic trees called multi-labeled phylogenetic trees, or MUL trees for short. One problem that relates to inferring a MUL tree is how to construct the smallest possible MUL tree that is consistent with a given set of rooted triplets, or SMRT problem for short. This problem is NP-hard. There is one algorithm for the SMRT problem which is exact and runs in O(7n) time, where n is the number of taxa. In this paper, we show that the SMRT does not seem to be an appropriate solution from the biological point of view. Indeed, we present a heuristic algorithm named MTRT for this problem and execute it on some real and simulated datasets. The results of MTRT show that triplets alone cannot provide enough information to infer the true MUL tree. So, it is inappropriate to infer a MUL tree using triplet information alone and considering the minimum number of duplications. Finally, we introduce some new problems which are more suitable from the biological point of view.

Download TeX format
back to top
scroll left or right